Article 4214

Title of the article

APPROACH TO NONDETERMINISTIC GAMES PROGRAMMING
(Part II: SPECIAL HEURISTICS AND EXAMPLES) 

Authors

Mel'nikov Boris Feliksovich, Doctor of physical and mathematical sciences, professor, sub-department of applied mathematics and informatics, Togliatti branch of Samara State University (31g Yubileynaya street, Togliatti, Russia), B.Melnikov@tltsu.ru
Mel'nikova Elena Anatol'evna, Candidate of physical and mathematical sciences, associate professor, sub-department of applied mathematics and informatics, Togliatti branch of Samara State University (31g Yubileynaya street, Togliatti, Russia), E.Melnikova@tltsu.ru
Radionov Aleksey Nikolaevich, Candidate of engineering sciences, associate professor, sub-department of applied mathematics and informatics, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), alx.radionov@gmail.com 

Index UDK

004.8.023, 004.83 

Abstract

Background. Creation of intellectual computer games is one of the main directions of artificial intelligence. Besides, computer games provide a wide range of various means used in education. The classical method for programming nondeterministic games for 2 users with full information is a minimax algorithm. In programming of nondeterministic games it is impossible to apply standard methods developed for deterministic games. The article is aimed at developing algorithms for nondeterministic games based on processing of a modified search tree of a game.
Materials and methods. The authors developed heuristics to order the top points in a nondeterministic search tree, that reduce the time of tree nodes processing and, consequently, allow to obtain an estimate of the investigated game position with greater probability, close to optimal. The authors also considered a possibility of simultaneous application of the nondeterministic search tree and the neural networks. The article adduces the performance examples of the suggested algorithms for constructing concrete estimates of top points (game positions) of various levels in the nondeterministic search tree. For practical application of the onsidered heuristics in game programs it is necessary to use the position estimator. The article describes the methods of formation and self-learning thereof. In algorithm performance examples the estimates’ values are chosen in such a way that the examples, regardless of their small size, would be interesting.
Results. The algorithms, developed by the authors, are realized in computer game programs; they also find application not just in nondeterministic games, but in other problems of discrete optimization as well.
Conclusions. Application of the heuristics, developed by the authors, allows to increase effectiveness of the algorithms for nondeterministic games programming – reduce the running time and capacity of used memory, improve game quality. 

Key words

algorithmics, nondeterministic games, search tree. 

Download PDF
References

1. Kormen T., Leyzerson Ch., Rivest R., Shtayn K. Algoritmy – postroenie i analiz [Algorithms – formation and analysis]. Moscow: Vil'yams, 2005, 1296 p.
2. Mel'nikov B. Kibernetika i sistemnyy analiz. NAN Ukrainy [Cybernetics and system analysis. National Academy of Sciences of Ukraine]. 2006, no. 3, pp. 32–42.
3. Melnikov B., Radionov A., Gumayunov V. 8th International Conference on Enterprise Information Systems. Paphos, Cyprus, 2006, pp. 360–364.
4. Melnikov B. 8th International Conference on High Performance Computing and Grid in Asia Pacific Region, IEEE Computer Society Press Ed. Beijing, China, 2005, pp. 73– 80.
5. Baumgertner S., Mel'nikov B. Vestnik Voronezhskogo gosudarstvennogo universiteta. Ser. Sist. analiz i inf. tekhnologii [Bulletin of Voronezh State University. Series: System analysis and information technologies]. 2010, no. 1, pp. 5–7.
6. Adel'son-Vel'skiy G., Arlazarov V., Donskoy M. Programmirovanie igr [Game programming]. Moscow: Nauka, 1978, 255 p.
7. Tesauro G. Commun. ACM. 1995, vol. 38, no. 3, pp. 58–68.
8. Mel'nikov B. Programmirovanie. Izvestiya RAN [Programming. Proceedings of the Russian Academy of Sciences]. 2001, no. 5, pp. 63–80.

 

Дата создания: 19.08.2014 09:26
Дата обновления: 02.09.2014 11:28